1. Technical Field
The present invention relates to computerized engineering layout of integrated circuit devices. More particularly, this invention relates to a method and system of removing hardware overlap.
2. Background Art
One of the first steps in manufacturing integrated circuit chips involve the laying out or designing of the circuits to be packaged on a chip. This step, commonly referred to as "floor planning," is typically accomplished using computer aided design ("CAD") layout tools. CAD tools allow chip manufacturers to plan the layout of the circuits on a computer where they can be analyzed and stored. Once the process of floor planning is complete, the designs can be transferred onto a chip using a variety of known methods and systems.
When designing hardware, engineering layout is one of the most significant aspects of the overall process. The cells, circuits and other types of hierarchical entities must be placed upon a chip or other type of packaging in an optimimal position, while conforming to various constraints that include timing and performance characteristics. To achieve a high level of performance, the actual physical location, or target location, of circuits, and their relational placement, are of critical importance. However, due to the high number (e.g., millions) of components that are required to be placed, a common problem, known as "overlap" often occurs. Overlap occurs when the floor planning software places two or more cells or circuits at the same physical location. Because it is undesirable to have two cells or circuits residing in the same physical location, some method of correction prior to actual manufacturing is required.
Presently, there are numerous methods of laying out circuits. Most attempt to deal at some level with the overlap problem. A first common floor planning method is referred to as annealing which uses a stochastic optimization algorithm. It does not eliminate overlap, but considers it as a cost constraint to be minimized. In its later stages, the algorithm attempts to remove as much overlap as possible, but fails to completely remove overlap since overlap is considered only one of many costs that make up the overall efficiency score given to any particular design. A second method of performing layout is referred to as recursive slicing or global placement. This process involves recursively partitioning the layout area into smaller and smaller areas. The recursive process terminates when the size of a cluster area meets the target specification for "smallness." This process normally leaves overlaps behind, and does not strive to remove them, as was the case in annealing, which considered overlap as one of the cost functions. In the case of recursive slicing, overlap removal is required prior to being able to complete the design in a meaningful way. Other scenarios include post-placement logic optimization and small changes to the underlying logic (referred to as engineering changes, or EC's) which must be incorporated in placement. In each of these cases, it is useful to quickly remove overlap, while minimizing perturbations to the design. EC's are typically roughly placed, and then overlap removal is performed.
Typical floor planning algorithms provide a reasonable level of effectiveness with respect to overlap removal, but are slow, complicated and generally fail to remove all cases of overlap. In addition, such systems do not fully respect design targets and move bounds when dealing with circuits or cells that overlap. Design targets refer to the desired physical location of the cell in question, while move bounds refer to areas on the device that contain circuits that are identified as "fixed in place" and therefore immovable. In such cases where move bounds are not considered, overlap removal has the potential of doing more harm than good, as certain timing critical circuits could be moved far off track from where they should be placed. Other violations could also be caused by ignoring move bounds during overlap removal.
An additional problem with existing systems that perform overlap removal as part of the overall floor planning effort is the amount of computational time involved. Typical systems require time proportional to N.sup.2 where N is the number of circuits on the device. Given the number of circuits a typical system must process, this creates a serious limitation. All of the above-mentioned art is hereby incorporated by reference.